package Top200;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-02-18 11:08
 */
public class threeSumClosest16 {
    public int twoSumClosest(int[] nums, int start, int target){
        int left=start,right=nums.length-1;
        int res=10000000;
        while (left<right){
            int sum=nums[left]+nums[right];
            int l=nums[left],r=nums[right];
            if (sum==target){
                return target;
            }
            if (Math.abs(sum-target)<Math.abs(res-target)){
                res=sum;
            }
            if (sum<target){
                while (left<right&&nums[left]==l){
                    left++;
                }
            }
            if (sum>target){
                while (left<right&&nums[right]==r){
                    right--;
                }
            }
        }
        return res;
    }
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res=10000000;
        for (int i = 0; i < nums.length; i++) {
            int twoSumClosest = twoSumClosest(nums, i + 1, target - nums[i]);
            int sum=twoSumClosest+nums[i];
            if (Math.abs(sum-target)<Math.abs(res-target)){
                res=sum;
            }
        }
        return res;
    }
}
